#
# 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
#
# 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
#
# 示例 1:
#
# 输入: [1,2,3,1]
# 输出: 4
# 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
#      偷窃到的最高金额 = 1 + 3 = 4 。
# 示例 2:
#
# 输入: [2,7,9,3,1]
# 输出: 12
# 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
#      偷窃到的最高金额 = 2 + 9 + 1 = 12 。

# 考查动态规划，基本思路是当前节点处最大值curMax = Math.max(curMax, curPrePreMax + cur)。举个例子[3, 2, 4, 7, 5, 6]
#
#  3     |                2                |            4           |         7            5           6
#
#        |   curPrePreMax：3                |  curMax：7             |    cur：7
#
# 那么经过上述公式计算，curMax = 10：
# 对于此题，如果只有两家或者以下，我们选择金额最大的。如果2家以上，那我们打劫到第 i 家的时候，就要考虑，要不要打劫这一家，
# 也就是（这一家的价值+打劫到 i - 2家的最大价值）和（打劫到上一家（i - 1）的最大价值），比较这两个值，选较大值作为打劫到第 i 家的最大价值。
# 最后输出最后一家就可以了。
class Solution:
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]
        curMax = nums[0]
        preMax = 0
        for i in range(1, len(nums)):
            temp = curMax
            curMax = max(nums[i] + preMax, curMax)
            preMax = temp
        return curMax

s = Solution()
test1 = [2,7,9,3,1]
test2 = [1,2,3,1]
print(s.rob([]))